#include <cstdio>
#include <cstdlib>

#include "ImageIO.h"
#include "Mesh.h"
#include "MeshIO.h"
#include "MeshMaterial.h"

#include <Triangle.h>
#include "Geometry.h"

#include <vector>
#include <iostream>

using namespace std;

class tree
{
    public:

        tree(tree *_pere, const int _profondeur) : pere(_pere), profondeur(_profondeur)
        {}

        tree(tree *_pere, std::vector<int> _numMesh) : pere(_pere), numMesh(_numMesh)
        {}

        ~tree()
        {
            delete[] fils;
            delete pere;
        }

        std::vector<int> numMesh;

        tree *fils[4];
        tree *pere;

        gk::BBox box;
        int profondeur;

};


class Quadtree
{
    public:
        Quadtree(const gk::Mesh *mesh, const gk::Transform& mvp, const gk::Transform& viewport, const int largeur, const int hauteur, const int profondeurMax);
        ~Quadtree();

        int subdivide(tree* element, const int w, const int h);
        void aff(tree* element);

        tree* getPere();
        std::vector<int> getEnsembleNumMesh(gk::Ray _ray, tree* element);

    private:
        tree *pere;
        const gk::Mesh *mesh;
        gk::Transform mvp;
        gk::Transform viewport;
        int profondeurMax;
};

Quadtree::Quadtree(const gk::Mesh *_mesh, const gk::Transform& _mvp, const gk::Transform& _viewport, const int _largeur, const int _hauteur, const int _profondeurMax) :
                    mvp(_mvp), viewport(_viewport), mesh(_mesh), profondeurMax(_profondeurMax)
{
    int n= mesh->triangleCount();

    std::vector<int> numMesh;
    numMesh.reserve(n);

    for(int i = 0; i < n; i++)
        numMesh.push_back(i);

    pere = new tree(NULL,numMesh);
    pere->profondeur = 0;

    subdivide(pere, _largeur, _hauteur);
}


Quadtree::~Quadtree()
{
    delete pere;
}

tree* Quadtree::getPere()
{
    return pere;
}


int Quadtree::subdivide(tree* element, const int w, const int h)
{

    if(element->numMesh.size() == 0 || element->profondeur == profondeurMax)
    {
        element->fils[0] = NULL;
        element->fils[1] = NULL;
        element->fils[2] = NULL;
        element->fils[3] = NULL;
    return 0;
    }

    // allocation des fils
    element->fils[0] = new tree(element,element->profondeur+1);
    element->fils[1] = new tree(element,element->profondeur+1);
    element->fils[2] = new tree(element,element->profondeur+1);
    element->fils[3] = new tree(element,element->profondeur+1);

    for(int i = 0; i < element->numMesh.size(); i++)
    {

        const gk::PNTriangle& t= mesh->getPNTriangle(element->numMesh[i]);

        gk::HPoint ha,hb,hc;
        gk::Point wa,wb,wc;
        mvp(t.a,ha); mvp(t.b,hb); mvp(t.c,hc);

        wa = viewport(ha.project());
        wb = viewport(hb.project());
        wc = viewport(hc.project());

        gk::Triangle T(wa,wb,wc);
        gk::Point centre = T.getUVPoint (0.33, 0.33);

        gk::BBox bboxT = t.getBBox();

        if(centre.x < w/2)
        {
            if(centre.y < h/2)
                {
                    element->fils[0]->numMesh.push_back(element->numMesh[i]);
                    element->fils[0]->box.Union(bboxT);
                }
            else
                {
                    element->fils[1]->numMesh.push_back(element->numMesh[i]);
                    element->fils[1]->box.Union(bboxT);
                }
        }
        else
        {
            if(centre.y < h/2)
                {
                    element->fils[2]->numMesh.push_back(element->numMesh[i]);
                    element->fils[2]->box.Union(bboxT);
                }
            else
                {
                    element->fils[3]->numMesh.push_back(element->numMesh[i]);
                    element->fils[3]->box.Union(bboxT);
                }
        }
    }

    if(element->fils[0]->numMesh.size() > 0)
        subdivide(element->fils[0], w/2, h/2);

    if(element->fils[1]->numMesh.size() > 0)
        subdivide(element->fils[1], w/2, h/2);

    if(element->fils[2]->numMesh.size() > 0)
        subdivide(element->fils[2], w/2, h/2);

    if(element->fils[3]->numMesh.size() > 0)
        subdivide(element->fils[3], w/2, h/2);

    return element->numMesh.size();
}

void Quadtree::aff(tree* _element)
{
    if(_element != NULL && _element->numMesh.size() > 0)
    {
        cout << "Prodonfeur : " << _element->profondeur << " Taille arbre : " <<_element->numMesh.size() << endl;
        cout << "BBox min : " << _element->box.pMin << " max " << _element->box.pMax << endl;
        aff(_element->fils[0]);
        aff(_element->fils[1]);
        aff(_element->fils[2]);
        aff(_element->fils[3]);
    }
}


vector<int> Quadtree::getEnsembleNumMesh(gk::Ray _ray, tree* _element)
{
//    if(_element->)

    if(_element->profondeur == profondeurMax) return _element->numMesh;

    float rt, ru;

    std::vector<int> retour;

    if(_element->fils[0]->numMesh.size() > 0)
        if(_element->fils[0]->box.Intersect(_ray, _ray.tmax ,rt ,ru))
        {
            vector<int> ens = getEnsembleNumMesh(_ray, _element->fils[0]);
            retour.insert(retour.end(), ens.begin(), ens.end());
        }

    if(_element->fils[1]->numMesh.size() > 0)
        if(_element->fils[1]->box.Intersect(_ray, _ray.tmax ,rt ,ru))
        {
            vector<int> ens = getEnsembleNumMesh(_ray, _element->fils[1]);
            retour.insert(retour.end(), ens.begin(), ens.end());
        }
//
    if(_element->fils[2]->numMesh.size() > 0)
        if(_element->fils[2]->box.Intersect(_ray, _ray.tmax ,rt ,ru))
        {
            vector<int> ens = getEnsembleNumMesh(_ray, _element->fils[2]);
            retour.insert(retour.end(), ens.begin(), ens.end());
        }

    if(_element->fils[3]->numMesh.size() > 0)
        if(_element->fils[3]->box.Intersect(_ray, _ray.tmax ,rt ,ru))
        {
            vector<int> ens = getEnsembleNumMesh(_ray, _element->fils[3]);
            retour.insert(retour.end(), ens.begin(), ens.end());
        }

    return retour;
}
